1548. Диагональ

Количество диагоналей у выпуклого n - угольника не менее N. Чему равно минимально возможное значение n?

Вход. Каждая входная стока содержит положительное целое число N (N £ 10¹⁵) – количество проведенных диагоналей. Значение N = 0 является концом входных данных и не обрабатывается.

Выход. Для каждого теста выведите его номер и минимально возможное число n сторон многоугольника.

Пример входа	Пример выхода
10 100 1000 0	Case 1: 7 Case 2: 16 Case 3: 47

РЕШЕНИЕ

математика

Анализ алгоритма

Каждая точка многоугольника соединена отрезками с n – 1 остальными точками. Эти отрезки образуют 2 стороны и n – 3 диагонали. Поскольку точек в многоугольнике n, а из каждой точки исходит n – 3 диагонали, то количество диагоналей выпуклого n – угольника равно n * (n – 3) / 2 (каждая диагональ подсчитывается дважды).

Если n * (n – 3) / 2 = N, то значение n находим из квадратного уравнения

n² – 3 * n – 2 * N = 0

Положительный корень уравнения равен

Остается округлить сверху вычисленное значение. Поскольку N £ 10¹⁵, то вычисления следует проводить, используя тип данных long long.

Пример

Рассмотрим второй тест. Для N = 100 получим

n = = 16

Реализация алгоритма

Читаем входные данные пока N > 0, вычисляем по формуле результат и выводим его с номером теста.

int cs = 1;

while(scanf("%lld",&n), n > 0)

{

res = int(ceil((3 + sqrtl(9.0 + 8*n)) / 2));

printf("Case %d: %d\n",cs,res);

cs++;

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n, cs = 1;

while((n = con.nextLong()) > 0)

{

long res = (int)(Math.ceil((3 + Math.sqrt(9 + 8*n))/2));

System.out.println("Case " + cs + ": " + res);

cs++;

}

}

}